class Solution {
    vector<int> price;
    vector<vector<int>> newSpecial;
    int n;

    // 记忆化搜索
    unordered_map<string, int> memo;

    int dfs(vector<int> needs)
    {
        string key;
        for(int &x : needs)
            key += to_string(x) + ',';
        if(memo.count(key))
            return memo[key];

        // 终止条件，判断needs数组中是否还有物品要购买
        bool done = true;
        for(int i = 0; i < n; i++)
            if(needs[i] > 0)
            {
                done = false;
                break;
            }

        if(done)    // 做完了，没有物品需要购买，返回 0
            return 0;

        // 不买礼包
        int minCost = 0;
        for(int i = 0; i < n; i++)
            minCost += price[i] * needs[i];

        // 买礼包
        for(vector<int> &special : newSpecial)
        {
            // 由于题目中说明：不能购买超出购物清单指定数量的物品
            // 所以需要判断这个礼包能不能购买
            bool valid = true;
            vector<int> tmpNeeds;
            for(int i = 0; i < n; i++)
            {
                int remain = needs[i] - special[i];
                if(remain < 0)
                {
                    // 礼包中对应物品大于本来所需要的，相当于多买了(special[i] > needs[i])
                    valid = false;
                    break;
                }
                tmpNeeds.push_back(remain);
            }

            // 礼包合法
            if(valid)
            {
                int res = dfs(tmpNeeds) + special[n];   // 购买礼包，并递归
                minCost = min(minCost, res);
            }
        }
        
        memo[key] = minCost;
        return minCost;
    }
public:
    int shoppingOffers(vector<int>& p, vector<vector<int>>& special, vector<int>& needs) {
        // 此题要预处理special数组，测试用例里面有两种不合理的礼包
        // 1. [0, 0, 100]，100块花了但是没作用
        // 2. [1, 3, +∞]，没有意义，还不如每个物品单买，不买这个礼包更好
        price = p;
        n = p.size();
        for(vector<int> &v : special)
        {
            bool valid = false;
            int cost = 0;
            for(int i = 0; i < n; i++)
            {
                cost += p[i] * v[i];
                if(v[i] > 0)    // 只有有一件物品大于 0 即可，起码花了钱可以买到礼包
                    valid = true;
            }
            // 礼包合理
            if(valid && cost > v[n])
                newSpecial.push_back(v);
        }

        return dfs(needs);
    }
};